[CF813D]Two Melodies

2019-12-24
#动态规划Dp
Codeforces

题意

在$\{a_i\}$中找出两个子序列（可以不连续），使得每个序列中相邻两数查为1或为7的倍数

求两个子序列长度和的最大值

题解

令 $f_{i,j}$表示前面两个断点分别在i和j的最大值

暴力$\theta(n^3)$转移，枚举断点，枚举原序列的数字均可

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i++){
	f[0][i] = 1;
	for (int k = i - 1; k >= 1; k--)
		for (int j = k - 1; j >= 0; j--){
			if (_abs(a[i] - a[k]) == 1 || a[i] % 7 == a[k] % 7) f[j][i] = max(f[j][i], f[j][k] + 1);
			if (_abs(a[i] - a[j]) == 1 || a[i] % 7 == a[j] % 7 || j == 0) f[k][i] = max(f[k][i], f[j][k] + 1);
		}
}
1
2
3
4
5
6
7
for (int i = 0; i <= n; i++){
	for (int j = i + 1; j <= n; j++)
		for (int k = 0; k < j; k++){
			if (_abs(a[j] - a[k]) == 1 || a[j] % 7 == a[k] % 7 || k == 0) f[i][j] = max(f[i][j], f[i][k] + 1);
			f[j][i] = f[i][j];
		}
}

对枚举断点的进行优化，记录所有$k\in [0,j-1]$的满足条件的Max即可

前一种比较难优化

调试记录

一开始写的没法优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
#include <cstring>
const int maxn = 5005;
using namespace std;
int f[maxn][maxn], n, a[maxn], Max1[maxn * 100], Max2[7];
int _abs(int x){return x < 0 ? -x : x;}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", a + i);
	for (int i = 0; i <= n; i++){
		memset(Max1, 0, sizeof Max1); memset(Max2, 0, sizeof Max2);
		for (int j = 1; j < i; j++)
			Max1[a[j]] = max(Max1[a[j]], f[i][j]),
			Max2[a[j] % 7] = max(Max2[a[j] % 7], f[i][j]);
		for (int j = i + 1; j <= n; j++){
			f[i][j] = max(f[i][j], max(Max1[a[j] - 1], Max1[a[j] + 1]) + 1);
			f[i][j] = max(f[i][j], f[i][0] + 1);
			f[i][j] = max(f[i][j], Max2[a[j] % 7] + 1);
			Max1[a[j]] = max(Max1[a[j]], f[i][j]);
			Max2[a[j] % 7] = max(Max2[a[j] % 7], f[i][j]);
			f[j][i] = f[i][j];
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; i++)
		for (int j = i + 1; j <= n; j++) ans = max(ans, f[i][j]);
	printf("%d\n", ans);
	return 0;
}